#ifndef TIM_STRING_H
#define TIM_STRING_H
#include"tim_vector.h"

namespace tim
{
	class string: public vector<char>
	{
		private:
			int match(const char* P)
			{
				int* next = buildNext(P);
				int n = (int) this->_size, i = 0;
				int m = (int) std::strlen(P), j = 0;

				while((j < m) and (i < n))
					if (0 > j || this->elem[i] == P[j]) {i++; j++;}
					else j = next[j];

				delete []next;
				return i - j;
			};//KMP算法，模式串回退到刚好正确的地方而费原点
			int* buildNext(const char* P)
			{
				int m = strlen(P), j = 0;
				int* N = new int[m];
				int t = N[0] = -1;

				while (j < m)
					if (0 > t || P[j] == P[t]) {
						j++; t++;
						N[j] = t;
					} else
						t = N[t];

				return N;
			};
			const char* char2chars(const char c)
			{
				char* all = new char[2];
				all[0] = c;
				all[1] = '\0';
				return all;
			}

		public:
			string(): vector<char>() {}
			string(std::string const& now)
			{
				for (char c: now)
					if (this->size() == 0) this->insert(0, c);
					else this->insert(this->size(), c);
			}//从标准string类生成，复杂度o（n）
			string(const char* s)
			{
				for (int i = 0; s[i] != '\0'; i++)
					if (this->size() == 0) this->insert(0, s[i]);
					else this->insert(this->size(), s[i]);
			}//从char字符串生成，复杂度o（n）
			string& operator+ (const char* s)
			{
				for (int i = 0; s[i] != '\0'; i++)
					if (this->size() == 0) this->insert(0, s[i]);
					else this->insert(this->size(), s[i]);

				return *this;
			}//重载char*加法
			string& operator+ (std::string s) { return this->operator+(s.c_str());}//重载string加法
			void operator+= (const char* s)
			{
				for (int i = 0; s[i] != '\0'; i++)
					if (this->size() == 0) this->insert(0, s[i]);
					else this->insert(this->size(), s[i]);
			}//重载char*加等
			void operator+= (std::string s) { this->operator+=(s.c_str()); }//重载string加等
			string& operator- (const char* s)
			{
				this->remove(match(s), match(s) + strlen(s));
				return *this;
			}//基于find的字符串减法
			string& operator- (std::string s) { return this->operator-(s.c_str());}
			void operator-= (const char* s) { this->remove(match(s), match(s) + strlen(s));}
			void operator-= (std::string s) { this->operator-=(s.c_str()); }
			string& operator+ (const char c) {return this->operator+(char2chars(c));};
			void operator+=(const char c) {this->operator+=(char2chars(c));};
			string& operator- (const char c) {return this->operator-(char2chars(c));};
			void operator-=(const char c) {this->operator-=(c);};//对于char的重载
			friend std::ostream& operator<<(std::ostream& out, string& now)
			{
				for (int i = 0; i < now._size; i++)
					std::cout<<now.elem[i];

				return out;
			}//重载输入
			friend std::istream& operator>>(std::istream& in, string& now)
			{
				std::string temp;
				in>>temp;
				for (int i = 0; i < temp.length(); i++) {
					if (now.size() == 0) now.insert(0, temp[i]);
					else now.insert(now.size(), temp[i]);
				}

				return in;
			}//重载输出
			int length() { return this->size(); }
			int find(const char* now) { return match(now); };//字符串匹配外接口
			int find(std::string now) { return match(now.c_str()); };
			int find(const char now) {return match(char2chars(now));};
			std::string& to_std_string()
			{
				std::string* temp = new std::string(this->elem);
				return *temp;
			}

			const char* c_str()//返回c风格字符串
			{
				char* temp = new char[this->size() + 1];
				for (int i = 0; i < this->size(); i++) temp[i] = this->elem[i];
				temp[this->size() + 1] = '\0';

				return temp;
			}
	};
}

#endif
